# -*- coding:utf-8 -*-


import numpy as np

import matplotlib.pyplot as plt

import matplotlib

import math

import pandas as pd

from random import random, randint, shuffle

import seaborn as sns  # 使用seaborn画图工具

matplotlib.rcParams['font.family'] = 'STSong'  # 设置字体


# 读取城市数据
def read_data():
    # 城市名数组
    city_name = []
    # 城市坐标数组
    city_condition = []
    # 通过open的方法打开txt文件输入数据
    with open('快递公司送货策略/data.txt', 'r', encoding='utf-8') as f:
        lines = f.readlines()  # 读取每一行数据
        # 处理每一行数据
        for line in range(len(lines)):
            lin = lines[line].split('\n')[0]
            # 数据通过空格和逗号分离出坐标x和坐标y以及城市名称
            lin = lin.split(',')
            # print(line)
            # 将分离出的城市名和城市地址放入数组中
            city_name.append(lin[0])
            city_condition.append([float(lin[1]), float(lin[2])])
    # 因为格式原因而转换成numpy数组
    city_condition = np.array(city_condition)
    # 返回处理后的结果
    return city_name, city_condition

# 定义TSP问题类


class TSP:

    def __init__(self, city_origin):
        # 设置起始点
        self.origin = city_origin
        # 设置进化次数
        self.epochTime = 2000
        # 设置种群数
        self.populationCount = 300
        # 设置保持率
        self.retainRate = 0.3
        # 设置变异率
        self.mutationRate = 0.2
        # 设置改良次数
        self.improveCount = 10000
        # 利用刚刚处理的read_data函数读取数据
        self.cityNames, self.condition = read_data()
        # 城市数目
        self.cityCounts = len(self.cityNames)
        # 生成距离矩阵
        self.mat = self.get_distance_matrix()
        # 城市索引
        self.cityIndex = [_ for _ in range(self.cityCounts)]
        self.cityIndex.remove(city_origin)
    # 生成距离矩阵
    def get_distance_matrix(self):
        # 使用短变量
        _cnt = self.cityCounts
        _cdt = self.condition
        # 生成矩阵
        _matr = np.zeros([_cnt, _cnt])
        for i in range(_cnt):
            for j in range(i, _cnt):
                if i == j:
                    _matr[i][j] = 0
                else:
                    x2 = abs(_cdt[i][0] - _cdt[j][0])
                    y2 = abs(_cdt[i][1] - _cdt[j][1])
                    _matr[j][i] = _matr[i][j] = x2 + y2
        mat = np.array(_matr)
        return _matr
    # 由路径求TSP路径总长度
    def get_total_distance(self, _x):
        # 使用短变量
        _matr = self.mat
        city_origin = self.origin
        # 计算长度
        city_dis = 0
        city_dis += _matr[city_origin][_x[0]]
        for _i in range(len(_x)):
            if _i == len(_x) - 1:
                city_dis += _matr[city_origin][_x[_i]]
            else:
                city_dis += _matr[_x[_i]][_x[_i + 1]]
        return city_dis
    # 生成一些较优秀的个体
    def improving(self, _x):
        # 改良次数
        improve_countes = self.improveCount
        i = 0 # 定义初始化计数器
        city_dis = self.get_total_distance(_x)
        while i < improve_countes:
            u = randint(0, len(_x) - 1)  # 随机生成两个整数
            v = randint(0, len(_x) - 1)  # 随机生成两个整数
            if u != v:
                new_xx = _x.copy()
                t = new_xx[u]
                new_xx[u] = new_xx[v]
                new_xx[v] = t
                new_distance = self.get_total_distance(new_xx)  # 调用自身方法
                if new_distance < city_dis:
                    city_dis = new_distance
                    _x = new_xx.copy()
            else:
                continue
            i += 1 # 控制计数器增加
        return _x

    # 自然选择

    def selection(self, _population):
        # 保持率
        retain_rate = self.retainRate
        # 对总距离从小到大进行排序
        graded_graded = [[self.get_total_distance(_x), _x] for _x in _population]
        graded_graded = [_x[1] for _x in sorted(graded_graded)]
        # 选出适应性强的染色体
        retain_length = int(len(graded_graded) * retain_rate)
        _parents = graded_graded[:retain_length]
        # 设置弱者的存活概率
        random_select_rate = 0.2
        # 选出适应性不强，但是幸存的染色体
        for chromosome in graded_graded[retain_length:]:
            if random() < random_select_rate:
                _parents.append(chromosome)
        return _parents

    # 交叉
    def crossovering(self, _parents):
        # 生成子代的个数,保证种群数目稳定
        target_count = self.populationCount - len(_parents)
        # 孩子列表
        child_cs = []
        while len(child_cs) < target_count:

            male_index = randint(0, len(_parents) - 1)

            female_index = randint(0, len(_parents) - 1)

            if male_index != female_index:

                male = _parents[male_index]

                female = _parents[female_index]

                left = randint(0, len(male) - 2)

                right = randint(left + 1, len(male) - 1)

                # 交叉片段

                gene1 = male[left:right]

                gene2 = female[left:right]

                child1_c = male[right:] + male[:right]

                child2_c = female[right:] + female[:right]

                child1 = child1_c.copy()

                child2 = child2_c.copy()

                for o in gene2:
                    child1_c.remove(o)

                for o in gene1:
                    child2_c.remove(o)

                child1[left:right] = gene2

                child2[left:right] = gene1

                child1[right:] = child1_c[0:len(child1) - right]

                child1[:left] = child1_c[len(child1) - right:]

                child2[right:] = child2_c[0:len(child1) - right]

                child2[:left] = child2_c[len(child1) - right:]

                child_cs.append(child1)

                child_cs.append(child2)

        return child_cs
    """
    广东工业大学 信息工程学院 饶XX
    """
    # 变异

    def mutation(self, _cs):
        # 变异率
        mutation_rate = self.mutationRate
        # 生成变异后结果
        child_cs = []
        for i in range(len(_cs)):
            child = _cs[i]
            if random() < mutation_rate:
                u = randint(1, len(child) - 4)
                v = randint(u + 1, len(child) - 3)
                w = randint(v + 1, len(child) - 2)
                child = child[0:u] + child[v:w] + child[u:v] + child[w:]
            child_cs.append(child)
        return child_cs
    # 得到最佳纯输出结果

    def get_best_result(self, _population):
        graded_graded = [[self.get_total_distance(_x), _x] for _x in _population]
        graded_graded = sorted(graded_graded)
        return graded_graded[0][0], graded_graded[0][1]

    # 进化
    def evolutioning(self):
        # 使用短变量
        city_origin = self.origin
        # 初始化种群
        population = []
        for i in range(self.populationCount):
            # 随机生成个体
            x = self.cityIndex.copy()
            shuffle(x)
            # 优化个体
            x = self.improving(x)
            # 添加
            population.append(x)
        # 遗传优化
        register = []
        i = 0
        distance, result_path = self.get_best_result(population)
        while i < self.epochTime:
            # 选择繁殖个体群
            parents = self.selection(population)  # 调用选择繁殖个体
            # 交叉繁殖
            child_cs = self.crossovering(parents)  # 调用交叉函数
            # 变异操作
            child_cs = self.mutation(child_cs)  # 调用变异方法
            # 更新种群
            population = parents + child_cs
            distance, result_path = self.get_best_result(population)
            register.append(distance)
            i += 1  # 计数器更新
        # 存储结论
        result_path = [city_origin] + result_path + [city_origin]
        # 输出
        # print(distance)
        print(result_path)
        # print(register)

        # 绘图

        xs = list()

        ys = list()

        _names = self.cityNames

        city_condition = self.condition

        for j in result_path:
            # 画注解

            plt.annotate(_names[j], [city_condition[j, 0], city_condition[j, 1]])

            xs.append(city_condition[j, 0])

            ys.append(city_condition[j, 1])

        # 绘图

        plt.xlabel('X')

        plt.ylabel('Y')

        plt.plot(xs, ys, '-o')

        plt.show()

        plt.xlabel('训练次数')

        plt.ylabel('距离')

        plt.plot(list(range(len(register))), register)

        # plt.show()




# 绘制距离热力图函数
def HeatMap(DataFrame):
    colormap = plt.cm.RdBu
    # DataFrame.columns = data.columns
    print(DataFrame.columns)
    ylabels = DataFrame.columns.values.tolist()
    f, ax = plt.subplots(figsize=(14, 14))
    ax.set_title('点与点距离图')

    # 设置展示一半，如果不需要注释掉mask即可
    mask = np.zeros_like(DataFrame)
    mask[np.triu_indices_from(mask)] = True

    with sns.axes_style("white"):
        sns.heatmap(DataFrame,
                    cmap="YlGnBu",
                    annot=True,
                    mask=mask,
                   )

    # print(DataFrame)
    # DataFrame.to_excel('灰色关联分析相关性图.xlsx')
    plt.show()


if __name__ == '__main__':
    ans = TSP(0)
    mat = ans.get_distance_matrix()
    mat = pd.DataFrame(mat)
    HeatMap(mat)
    ans.evolutioning()
